package doublelinkedlist

import (
	"fmt"
	"sync"
)

type Node[T any] struct {
	element T
	prev    *Node[T]
	next    *Node[T]
}

// LinkedList 双向链表
/*
nil|first|next  <->  prev|node|next <->  ... prev|last|nil
*/
type LinkedList[T any] struct {
	size  int
	first *Node[T]
	last  *Node[T]
	mux   sync.RWMutex
}

// New 返回一个双向链表
func New[T any]() *LinkedList[T] {
	return new(LinkedList[T])
}

// at e at.next
func (l *LinkedList[T]) insertAfter(at, e *Node[T]) {
	l.mux.Lock()
	defer l.mux.Unlock()
	if at == nil {
		l.first = e
		l.last = e
		l.size++
		return
	}

	// a  e -> a.next
	e.next = at.next
	// a <-  e -> a.next
	e.prev = at
	// a <-  e <-> a.next
	if at.next != nil {
		at.next.prev = e
	} else {
		l.last = e
	}
	// a <->  e <-> a.next
	at.next = e
	l.size++
}

// at.prev e at
func (l *LinkedList[T]) insertBefore(at, e *Node[T]) {
	l.mux.Lock()
	defer l.mux.Unlock()
	if at == nil {
		l.first = e
		l.last = e
		l.size++
		return
	}

	// at.prev  e -> at
	e.next = at
	// at.prev -> e -> at
	if at.prev == nil {
		//e -> at
		l.first = e
		l.first.next = at
	} else {
		// at.prev <-> e -> at
		at.prev.next = e
		e.prev = at.prev
	}
	// at.prev <-> e <-> at
	at.prev = e
	l.size++
}

// Append node 追加一组数据
func (l *LinkedList[T]) Append(element ...T) {
	for _, v := range element {
		l.insertAfter(l.last, &Node[T]{
			element: v,
		})
	}
}

func (l *LinkedList[T]) LPush(element T) {
	l.insertBefore(l.first, &Node[T]{
		element: element,
	})
}

func (l *LinkedList[T]) RPush(element T) {
	l.insertAfter(l.last, &Node[T]{element: element})
}

// LPop 左边弹出
func (l *LinkedList[T]) LPop() (element T, err error) {
	node := l.first
	err = l.Remove(node)
	if err != nil {
		return element, err
	}
	//l.mux.Lock()
	//defer l.mux.Unlock()
	//node := l.first
	//// nil|first|next <-> prev|at|next  prev|last|nil
	//if l.size > 1 {
	//	//node := l.first
	//	l.first = l.first.next
	//	l.first.prev = nil
	//	node.next = nil
	//	l.size--
	//} else if l.size == 1 { // nil|first&last|nil
	//	l.first = nil
	//	l.last = nil
	//	l.size--
	//} else { // nil
	//	return element, fmt.Errorf("list is empty")
	//}
	return node.element, nil
}

// RPop 左边弹出
func (l *LinkedList[T]) RPop() (element T, err error) {
	node := l.last
	err = l.Remove(node)
	if err != nil {
		return element, err
	}
	//l.mux.Lock()
	//defer l.mux.Unlock()
	// nil|first|next <-> prev|at|next  prev|last|nil
	//if l.size > 1 {
	//	l.last = l.last.prev
	//	l.last.next = nil
	//	node.prev = nil
	//	l.size--
	//} else if l.size == 1 { // nil|first&last|nil
	//	l.first = nil
	//	l.last = nil
	//	l.size--
	//} else {
	//	return element, fmt.Errorf("list is empty")
	//}
	// nil
	return node.element, nil
}

// Remove 删除某个node
func (l *LinkedList[T]) Remove(e *Node[T]) error {
	l.mux.Lock()
	defer l.mux.Unlock()
	// nil|first|next <-> prev|at|next <->  prev|last|nil
	if l.size > 1 {
		if e.prev != nil {
			e.prev.next = e.next
		} else {
			l.first = e.next
		}
		if e.next != nil {
			e.next.prev = e.prev
		} else {
			l.last = e.prev
		}
		e.prev = nil
		e.next = nil
		l.size--
	} else if l.size == 1 {
		l.first = nil
		l.last = nil
		l.size--
	} else {
		return fmt.Errorf("list is empty")
	}
	return nil
	// nil|first&last|nil
	// nil
}
func (l *LinkedList[T]) ForEach() {
	for e := l.first; e != nil; e = e.next {
		fmt.Println(e.element)
	}
}
